#pragma once
#include <iostream>
#include <vector>
#include <map>
#include <string>


namespace dzp
{
    
    template<class T>
    class UnionFindSet1
    {
        private:
        std::vector<std::string> ve;  //使用编号查名字
        std::map<std::string,int> ma;  //使用名字查编号
        public:
        UnionFindSet1(const T* _ve,size_t n)
        {
            for(int i=0;i<n;i++)
            {
                ve.push_back(_ve[i]);
                ma[_ve[i]]=i;
            }
        }
    };

    //查集合
    //template<class T>
    class UnionFindSet
    {
        private:
        std::vector<int> ve;
        public:
        UnionFindSet(size_t n)
        :ve(n,-1)
        {}

        //查找成员的根/父亲的
        size_t FindRoot(int x)
        {
            int root=x;
            //比如9号成员 在ve[9]的值是负数 表示9号就是根，
            while(ve[root]>=0)
            {
                //9号不是根 就把9号的父亲节点给X
                root=ve[root];
            }
            //路径压缩
            while(ve[x]>=0)
            {
                int parent=ve[x];
                ve[x]=root;
                x=parent;
            }
            return root;
        }

        //合并集合
        void Union(int x,int y)
        {
            //找到它们的根节点
            int root1=FindRoot(x);
            int root2=FindRoot(y);
            if(root1==root2)
            return ;


            //合并集合
            //把小集合的合并到大集合中
            if(abs(root1)<abs(root2))
                std::swap(root1,root2);

                ve[root1]+=ve[root2];
                ve[root2]=root1;
            
        }

        //查找有几个集合
        size_t SetCount()
        {
            size_t size=0;
            for(int i=0;i<ve.size();i++)
            {
                if(ve[i]<0)
                size++;
            }
            return size;
        }

        //判断是否是一个集合
        bool InSet(const int& x1,const int& x2)
        {
            return FindRoot(x1)==FindRoot(x2);
        }
        void ff()
        {
            for(int i=0;i<ve.size();i++)
            {
                std::cout<<"["<<i<<"]"<<ve[i]<<" ";
            }
        }
    };
}